package com.shm.leetcode;

/**
 * 415. 字符串相加
 * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
 *
 *  
 *
 * 提示：
 *
 * num1 和num2 的长度都小于 5100
 * num1 和num2 都只包含数字 0-9
 * num1 和num2 都不包含任何前导零
 * 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/2021-spring-recruitment/5jcm1i/
 * @author SHM
 */
public class AddStrings {
    /**
     *
     * @param num1
     * @param num2
     * @return
     */
    public String addStrings(String num1, String num2) {
        int n =num1.length();
        int m =num2.length();
        int i=n-1,j=m-1;
        StringBuilder sb= new StringBuilder();
        int a=0;
        while(i>=0&&j>=0){
            int val = num1.charAt(i)-'0' + num2.charAt(j)-'0'+a;
            if (val>=10){
                val -= 10;
                a=1;
            }else {
                a=0;
            }
            sb.append(val);
            i--;
            j--;
        }
        if(i>=0){
            while (i>=0){
                int val = num1.charAt(i)-'0'+a;
                if (val>=10){
                    val -= 10;
                    a=1;
                }else {
                    a=0;
                }
                sb.append(val);
                i--;
            }
        }

        if(j>=0){
            while (j>=0){
                int val = num2.charAt(j)-'0'+a;
                if (val>=10){
                    val -= 10;
                    a=1;
                }else {
                    a=0;
                }
                sb.append(val);
                j--;
            }
        }

        if(a==1){
            sb.append(1);
        }
        return sb.reverse().toString();
    }

    /**
     * 方法一：模拟
     * 思路与算法
     *
     * 本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是如下图将相同数位对齐，从低到高逐位相加，如果当前位和超过 1010，则向高位进一位？因此我们只要将这个过程用代码写出来即可。
     *
     *
     *
     * 具体实现也不复杂，我们定义两个指针 ii 和 jj 分别指向 \textit{num1}num1 和 \textit{num2}num2 的末尾，即最低位，同时定义一个变量 \textit{add}add 维护当前是否有进位，然后从末尾到开头逐位相加即可。你可能会想两个数字位数不同怎么处理，这里我们统一在指针当前下标处于负数的时候返回 00，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理，具体可以看下面的代码。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(\max(\textit{len}_1,\textit{len}_2))O(max(len
     * 1
     * ​
     *  ,len
     * 2
     * ​
     *  ))，其中 \textit{len}_1=\textit{num1}.\textit{length}len
     * 1
     * ​
     *  =num1.length，\textit{len}_2=\textit{num2}.\textit{length}len
     * 2
     * ​
     *  =num2.length。竖式加法的次数取决于较大数的位数。
     * 空间复杂度：O(1)O(1)。除答案外我们只需要常数空间存放若干变量。在 Java 解法中使用到了 StringBuffer，故 Java 解法的空间复杂度为 O(n)O(n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/
     * @param num1
     * @param num2
     * @return
     */
    public String addStrings_2(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }
}
